package swardToOffer.struct_6_bit_operation;

/**
 * @Author ChanZany
 * @Date 2021/5/24 16:58
 * @Version 1.0
 * <p>
 * 面试题43：从1到n整数中1出现的次数
 * 题目：输入一个整数n，求从1到n这n个整数的十进制表示中1出现的次数。例如
 * 输入12，从1到12这些整数中包含1 的数字有1，10，11和12，1一共出现了5次。
 * <p>
 * 方法1:暴力破解,遍历每个数并且对每个数进行取余和除10操作.余数为1则count++
 * 方法2:找规律
https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/solution/mian-shi-ti-43-1n-zheng-shu-zhong-1-chu-xian-de-2/
 */
public class NumberOf1 {

    public int countDigitOne(int n) {
        int digit = 1, res = 0;
        int high = n / 10, cur = n % 10, low = 0;
        while(high != 0 || cur != 0) {
            if(cur == 0) res += high * digit;
            else if(cur == 1) res += high * digit + low + 1;
            else res += (high + 1) * digit;
            low += cur * digit;
            cur = high % 10;
            high /= 10;
            digit *= 10;
        }
        return res;
    }

    public static void main(String[] args) {
        NumberOf1 Main = new NumberOf1();
        System.out.println(Main.countDigitOne(12));
    }
}
